package com.lsa.iview.chap2;

import junit.framework.Assert;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import com.lsa.helpers.IClosure1;
import com.lsa.helpers.ISimpleClosure;
import com.lsa.helpers.SingleLinkedList;
import com.lsa.helpers.SingleLinkedList.ListNode;
import com.lsa.helpers.Utils;

public class LinkedListQuestionsTest {
	@Test
	public void testRemoveDuplicatesWithStorage() throws Exception {
		testRemoveDuplicatesWithStorage("1 2 2 1 3 4 5 6 6", "1 2 3 4 5 6");
		testRemoveDuplicatesWithStorage("1 2 3 4 5 6", "1 2 3 4 5 6");
		testRemoveDuplicatesWithStorage("1 1 1 1 1 1", "1");
		testRemoveDuplicatesWithStorage("1", "1");
		testRemoveDuplicatesWithStorage("1 1 1 2 3 3 3", "1 2 3");
	}
	
	@Test
	public void testRemoveDuplicatesNoStorage() throws Exception {
		testRemoveDuplicatesNoStorage("1 2 2 1 3 4 5 6 6", "1 2 3 4 5 6");
		testRemoveDuplicatesNoStorage("1 2 3 4 5 6", "1 2 3 4 5 6");
		testRemoveDuplicatesNoStorage("1 1 1 1 1 1", "1");
		testRemoveDuplicatesNoStorage("1", "1");
		testRemoveDuplicatesNoStorage("1 1 1 2 3 3 3", "1 2 3");
	}
	
	@Test
	public void testNthToTheLast() throws Exception {
		class NthToTheLast implements IClosure1<SingleLinkedList<Integer>, ListNode<Integer>, Integer, Exception>{
			@Override
			public ListNode<Integer> invoke(SingleLinkedList<Integer> l,
					Integer n) throws Exception {
				return LinkedListQuestions.nthToTheLast(l, n);
			}
		};
		
		NthToTheLast closure = new NthToTheLast();
		testNthToTheLast(closure);
	}
	
	@Test
	public void testNthToTheLastQuadratic() throws Exception {
		class NthToTheLast implements IClosure1<SingleLinkedList<Integer>, ListNode<Integer>, Integer, Exception>{
			@Override
			public ListNode<Integer> invoke(SingleLinkedList<Integer> l,
					Integer n) throws Exception {
				return LinkedListQuestions.nthToTheLastQuadratic(l, n);
			}
		};
		
		NthToTheLast closure = new NthToTheLast();
		testNthToTheLast(closure);
	}
	
	@Test
	public void testNthToTheLastRec() throws Exception {
		class NthToTheLast implements IClosure1<SingleLinkedList<Integer>, ListNode<Integer>, Integer, Exception>{
			@Override
			public ListNode<Integer> invoke(SingleLinkedList<Integer> l,
					Integer n) throws Exception {
				return LinkedListQuestions.nthToTheLastRecursive(l, n);
			}
		};
		
		NthToTheLast closure = new NthToTheLast();
		testNthToTheLast(closure);
	}
	
	@Test
	public void testSimulateAddition() throws Exception {
		testSimulateAddition("5 9", "5 8", "0 8 1");
		testSimulateAddition("0", "0", "0");
		testSimulateAddition("0 1", "5", "5 1");
		testSimulateAddition("5 6", "6", "1 7");
		
		for (int i = 0; i < 100; i++) {
			int n1 = Utils.random(1, 1000);
			int n2 = Utils.random(1, 1000);
			
			int r = n1 + n2;
			
			testSimulateAddition(toListNotation(n1), toListNotation(n2), toListNotation(r));
		}
	}
	
	@Test
	public void testFindCircle() throws Exception {
		SingleLinkedList<Integer> list = Utils.createSingleLinkedListWithCirculars("1 2 3 4 5");
		ListNode<Integer> nodeCircleStart = LinkedListQuestions.findCircle(list);
		Assert.assertNull(nodeCircleStart);
		
		list = Utils.createSingleLinkedListWithCirculars("1 2 3 4 5 2");
		nodeCircleStart = LinkedListQuestions.findCircle(list);
		Assert.assertNotNull(nodeCircleStart);
		
		list = Utils.createSingleLinkedListWithCirculars("1 2 3 4 5 6 7 8 9 10 11 4");
		nodeCircleStart = LinkedListQuestions.findCircle(list);
		Assert.assertNotNull(nodeCircleStart);
		System.out.println(nodeCircleStart);
	}
	
	private String toListNotation(int n) {
		String s = n + "";
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < s.length(); i++) {
			res.append(" " + s.charAt(i));
		}
		return StringUtils.reverse(res.toString());
	}

	private void testSimulateAddition(String data1, String data2,
			String dataExpected) {
		SingleLinkedList<Integer> n1 = Utils.createSingleLinkedListOfInteger(data1);
		SingleLinkedList<Integer> n2 = Utils.createSingleLinkedListOfInteger(data2);
		SingleLinkedList<Integer> r = LinkedListQuestions.simulateAddition(n1, n2);
		
		SingleLinkedList<Integer> expect = Utils.createSingleLinkedListOfInteger(dataExpected);
		Assert.assertTrue(String.format("n1 %s, n2 %s, Expected %s, got %s", n1.toString(), n2.toString(), expect.toString(), r.toString()), r.equals(expect));
	}
	
	private void testNthToTheLast(IClosure1<SingleLinkedList<Integer>, ListNode<Integer>, Integer, Exception> nthToTheLast) throws Exception {
		SingleLinkedList<Integer> singleList = Utils.createSingleLinkedListOfInteger("1 2 3 4 5 6 7");
		ListNode<Integer> node = nthToTheLast.invoke(singleList, 0);
		Assert.assertEquals(7, (int)node.data);
		
		node = nthToTheLast.invoke(singleList, 1);
		Assert.assertEquals(6, (int)node.data);
		
		node = nthToTheLast.invoke(singleList, 5);
		Assert.assertEquals(2, (int)node.data);
		
		node = nthToTheLast.invoke(singleList, 6);
		Assert.assertEquals(1, (int)node.data);
		
		node = nthToTheLast.invoke(singleList, 7);
		Assert.assertNull(node);
		
		for (int i = 7; i < 21; i++) {
			node = nthToTheLast.invoke(singleList, i);
			Assert.assertNull(node);
		}
	}
	
	private void testRemoveDuplicatesWithStorage(String data, String expected) throws Exception {
		testRemoveDuplicates(data, expected, new ISimpleClosure<SingleLinkedList<Integer>>() {
			@Override
			public Void invoke(SingleLinkedList<Integer> singleList)  {
				LinkedListQuestions.removeDuplicatesWithStorage(singleList);
				return null;
			}
		});
	}
	
	private void testRemoveDuplicatesNoStorage(String data, String expected) throws Exception {
		testRemoveDuplicates(data, expected, new ISimpleClosure<SingleLinkedList<Integer>>() {
			@Override
			public Void invoke(SingleLinkedList<Integer> singleList)  {
				LinkedListQuestions.removeDuplicatesNoStorage(singleList);
				return null;
			}
		});
	}
	
	private void testRemoveDuplicates(String data, String expected, ISimpleClosure<SingleLinkedList<Integer>> removeDuplicatesRoutine) throws Exception {
		SingleLinkedList<Integer> singleList = Utils.createSingleLinkedListOfInteger(data);
		removeDuplicatesRoutine.invoke(singleList);
		
		SingleLinkedList<Integer> expectedResultList = Utils.createSingleLinkedListOfInteger(expected);
		Assert.assertTrue(singleList.equals(expectedResultList));
//		System.out.println("----------------------------------");
//		Utils.print(singleList.toCollection());
	}
}
